//347 求前K个最频繁的数字
/*
给定一个数组，求前 k 个最频繁的数字

输入输出样例：
	输入是一个数组和一个目标值 k。输出是一个长度为 k 的数组

Input: nums = [1,1,1,1,2,2,3,4], k = 2
Output: [1,2]





*/
vector<int> topKFrequent(vector<int> &nums, int k)
{
	unordered_map<int, int> counts;
	int max_count = 0;
	for (const int &num : nums)
	{
		max_count = max(max_count, ++counts[num]);
	}
	vector<vector<int>> buckets(max_count + 1);
	for (const auto &p : counts)
	{
		buckets[p.second].push_back(p.first);
	}
	vector<int> ans;
	for (int i = max_count; i >= 0 && ans.size() < k; --i)
	{
		for (const int &num : buckets[i])
		{
			ans.push_back(num);
			if (ans.size() == k)
			{
				break;
			}
		}
	}
	return ans;
}